package nl.unimaas.games.tron.player;

import java.awt.Color;
import java.lang.reflect.Field;
import java.util.ArrayList;

import org.w3c.dom.NamedNodeMap;

import nl.unimaas.games.tron.engine.Board;
import nl.unimaas.games.tron.engine.Evaluator.SpaceEvaluator;
import nl.unimaas.games.tron.player.mcts.CutOffStrategy;
import nl.unimaas.games.tron.player.mcts.FinalNodeSelectionStrategy;
import nl.unimaas.games.tron.player.mcts.NGramPlayout;
import nl.unimaas.games.tron.player.mcts.Node;
import nl.unimaas.games.tron.player.mcts.SolverNode;
import nl.unimaas.games.tron.player.mcts.SolverSelectionStrategy;

/** 2-player game */
@SuppressWarnings("serial")
public class NGramMCTSSolverPlayer extends Player {

    protected static boolean DEBUG = false;
    private final static double SIM_WIN = 1, SIM_DRAW = 0, SIM_LOSS = -1;
    protected long MAX_TURN_TIME = 1000;
    private int turn = 0;
    protected SolverNode root;
    protected Board rootBoard, currentBoard;
    protected boolean applySpaceEstimation;
    protected boolean applyExpansionCutOff = false;
    protected boolean applySimulationCutOff = false;
    private boolean endgame = false;
    protected SolverSelectionStrategy select = SolverSelectionStrategy.UCT;
    protected NGramPlayout playout = new NGramPlayout(15, 0.3, true);
    protected FinalNodeSelectionStrategy finalMove = FinalNodeSelectionStrategy.SECURE_SOLVED_CHILD;
    protected CutOffStrategy cutOff = CutOffStrategy.SPACE;
    protected SpaceEvaluator spaceEval = new SpaceEvaluator();

    public NGramMCTSSolverPlayer(String name, int num, Color c) {
        super(name, num, c);
    }

    @Override
    protected int computeMove(Board b, long endTime) {
        turn++;
        applySpaceEstimation = (applyExpansionCutOff || applySimulationCutOff);
        try {
            long start = System.currentTimeMillis();
            if (DEBUG) {
                System.out.println();
            }

            if (root == null) {//first move of the game 
                turn = 0;
                endgame = false;
                root = createNode(1 - getNumber(), null, Board.MOVE_NONE, b);
                onComputeFirstMove(root);
            }
            rootBoard = b;

            if (endTime == 0) {
                endTime = System.currentTimeMillis() + MAX_TURN_TIME;
            }

            int move = MCTSSolver(root, endTime);
            //After each MCTS, reset the ngram. Board state has changed.
            this.playout.resetNGram();
            if (DEBUG) {
                System.out.println("PERFORM MOVE " + Board.moveToString(move) + " (in " + (System.currentTimeMillis() - start) + " ms) at T" + turn);
            }
            return move;
        } catch (Exception e) {
            e.printStackTrace();
            System.out.println("error in MCTSSolverPlayer! " + e.getMessage());
            return Board.MOVE_NONE;
        }
    }

    @Override
    public synchronized void onPlayerMove(final Board b, int playerNr, int move) {
        if (playerNr == getNumber()) {
            return;
        }

        if (root.children.isEmpty()) {
            throw new IllegalStateException("root has no children");
        }
        for (int i = 0; i < root.children.size(); i++) {
            Node child = root.children.get(i);
            if (child.move == move) {
                child.parent.apply(rootBoard);
                child.parent = null;
                root = (SolverNode) child;
                child.apply(rootBoard);
                if (!rootBoard.equals(b)) {
                    rootBoard.print();
                    b.print();
                    throw new IllegalStateException("boards do not match");
                }
                return;
            }
        }
        throw new IllegalStateException("cannot move to the correct state");
    }

    protected int MCTSSolver(SolverNode root, long endTime) {
        //System.out.println("I have " + (endTime - System.currentTimeMillis()) + " ms to compute a result");
        if (endTime - System.currentTimeMillis() < 100) {
            System.err.println("MCTS: I have less than 100 ms to compute a result!");
        }
        SolverNode current;
        currentBoard = rootBoard.deepClone(false);
        int its = 0, endIts = 0, cuts = 0;
        double r;

        if (root.proven) {
            //System.out.println("endgame!!!!!!!!!! proof");
        }

        if (root.prediction != CutOffStrategy.UNDECIDED) {
            endgame = true;
            //System.out.println("endgame!!!!!!!!!! space");
            root.prediction = CutOffStrategy.UNDECIDED;
            root.expanded = false;
        }

        if (DEBUG && root.children.isEmpty()) {
            System.out.println("Root has no children");
        }
        root.proven = false;
        root.prediction = CutOffStrategy.UNDECIDED;

        while (System.currentTimeMillis() < endTime && !root.proven) {
            current = root;
            rootBoard.copyTo(currentBoard, false);

            if (root.proven) {
                System.out.println("Not going to bother with this proven root");
                break;
            }

            while (!current.isLeaf() && current.expanded) {
                current = select(current);
                if (current == null) {
                    break;
                }
            }

            if (current == null) {
                continue;
            }

            //check for a possible game cut off
            r = 0;
            expand(current, currentBoard);

            if (current.children.isEmpty()) {
                int myNr = current.playerNr;
                int startingPlayer = myNr;
                int otherNr = 1 - myNr;
                if (myNr == getNumber()) {
                    startingPlayer = otherNr;
                }
                // terminal state //
                if (current.prediction == CutOffStrategy.UNDECIDED) {
                    //the other player has no more moves
                    int myPos = currentBoard.getPlayerPosition(current.playerNr);
                    int otherPos = currentBoard.getPlayerPosition(1 - current.playerNr);
                    if (myPos == otherPos) {
                        this.playout.onFinishPlayout(startingPlayer, myNr, SIM_DRAW, true);
                        r = SIM_DRAW; //crash -> draw
                    } else {
                        //check if we have any moves left
                        if (currentBoard.getValidMoveCount(Board.posToX(myPos), Board.posToY(myPos)) == 0) {
                            this.playout.onFinishPlayout(startingPlayer, myNr, SIM_DRAW, true);
                            r = SIM_DRAW; //both players are stuck -> draw
                        } else {
                            this.playout.onFinishPlayout(startingPlayer, myNr, SIM_WIN, true);
                            r = SIM_WIN; //we can still move -> win
                        }
                    }
                } else {
                    if (current.prediction == CutOffStrategy.CURRENT_PLAYER_WON) {
                        this.playout.onFinishPlayout(startingPlayer, myNr, SIM_WIN, true);
                        r = SIM_WIN;
                    } else if (current.prediction == CutOffStrategy.OTHER_PLAYER_WON) {
                        this.playout.onFinishPlayout(startingPlayer, myNr, SIM_LOSS, true);
                        r = SIM_LOSS;
                    } else {
                        this.playout.onFinishPlayout(startingPlayer, myNr, SIM_DRAW, true);
                        r = SIM_DRAW;
                    }
                }

                double p_r = r;
                if (current.isOpponentNode()) {
                    p_r *= -1;
                }

                current.pess = p_r;
                current.opti = p_r;
                current.proven = true;

                propagatePessimisticBound(current);
                propagateOptimisticBound(current);
                //update the 'proven' field
                SolverNode cur = current;
                do {
                    if (!cur.checkIfProven()) {
                        break;
                    }
                    cur = (SolverNode) cur.parent;
                } while (cur != null);
                endIts++;
            } else {
                current = select(current);
                if (current == null) {
                    continue;
                }
                if (current.proven) {
                    System.err.println("Prooooven nodeee");
                }
                //simulation starts from one of our moves, player 2 moves first
                r = simulate(current, currentBoard);
                its++;
            }

            /* Backpropagation phase*/
            do {
                current.value += r;
                if (r == 0) {
                    current.draws++;
                } else if (r > 0) {
                    current.wins++;
                }

                r *= -1;
                current.visits++;
                current = (SolverNode) current.parent;
            } while (current != null);
        }

        //System.out.println("Solver Simulations: " + its);
        if (DEBUG) {
            System.out.println("Simulations: " + its + "  Proof passes: " + endIts + " Cuts: " + cuts);
            System.out.println("Root: " + root);
            System.out.println("Root visits: " + root.visits);
            System.out.println("Root children: ");
            root.printChildren();
        }

        for (int i = 0; i < root.children.size(); i++) {
            SolverNode c = (SolverNode) root.children.get(i);
            if (DEBUG && c.proven && c.opti == 1 && c.pess == 1) {
                System.err.println("Playing " + Board.moveToString(c.move) + " is a guaranteed win!");
            }
        }
        SolverNode prevRoot = root;

        if (root.children.isEmpty()) {
            System.err.println("Root has no children!");
        }

        root = (SolverNode) finalMove.getNode(root);

        if (root == null) {
            System.err.println("Got null from finalMove.getNode(root)!");
        }

        //root.parent.printChildren();

        this.root = root;
        if (root.children.isEmpty()) {
            root.expanded = false;
            root.prediction = CutOffStrategy.UNDECIDED;
            root.spaceDiff = Double.NaN;
            root.proven = false;
            rootBoard.copyTo(currentBoard, false);
            root.apply(currentBoard);
            expand(root, currentBoard);
        }
        if (DEBUG && root.proven) {
            System.out.println("Root proven!");
        }
        onFinishComputation(root);
        //discard the upper part of the tree
        root.parent = null;
        if (DEBUG) {
            System.out.println("Best node: " + root);
        }
        return root.move;
    }

    /** Selects a child node of the current node */
    protected SolverNode select(SolverNode node) {
        SolverNode n = (SolverNode) select.getNode(node);
        if (n == null) {
            if (DEBUG && false) {
                System.err.println("no non-proven child node to select");
            }
        } else {
            n.apply(currentBoard);
        }
        return n;
    }

    protected void expand(SolverNode node, Board board) {
        if (!node.expanded) {
            //the other player performs a move
            int myNr = 1 - node.playerNr;
            node.expanded = true;
            //pre-create all nodes
            int myPos = board.getPlayerPosition(myNr);
            int myX = Board.posToX(myPos), myY = Board.posToY(myPos);

            ArrayList<Integer> moves = board.getValidMoves(myX, myY);
            if (!endgame && applyExpansionCutOff
                    && node.playerNr != getNumber()
                    && !moves.isEmpty()
                    && !node.isRoot()) {
                node.spaceDiff = spaceEval.compute(board, node.playerNr);
                node.connected = spaceEval.isConnected();
                node.prediction = cutOff.getEnding(node, board);
            }

            if (node.prediction == CutOffStrategy.UNDECIDED) {
                for (int m : moves) {
                    Node n = createNode(myNr, node, m, board);
                    node.children.add(n);
                }

                //since we moved first, the current player (2) might be able turn the game into a draw
                if (myNr != getNumber()) {
                    int otherNr = node.playerNr;
                    int otherPos = board.getPlayerPosition(otherNr);
                    int otherX = Board.posToX(otherPos), otherY = Board.posToY(otherPos);
                    if (Board.getManhattanDistance(myX, myY, otherX, otherY) == 1) {
                        int m = Board.getMoveFromPositions(myX, myY, otherX, otherY);
                        Node n = createNode(myNr, node, m, board);
                        n.expanded = true;
                        node.children.add(n);
                    }
                }
            }
        }
    }

    /** Simulates a game from the viewpoint of the player of the given node */
    protected double simulate(final SolverNode node, Board board) {
        int myMove, otherMove;

        int myNr = node.playerNr;
        int myPos = board.getPlayerPosition(myNr);
        int myX = Board.posToX(myPos), myY = Board.posToY(myPos);
        //get position
        int otherNr = 1 - node.playerNr;
        int otherPos = board.getPlayerPosition(otherNr);
        int otherX = Board.posToX(otherPos), otherY = Board.posToY(otherPos);

        int startingPlayer = myNr;
        if (myNr == getNumber()) {
            startingPlayer = otherNr;
            //player 2 still has to perform a move first
            otherMove = playout.getMove(board, otherX, otherY, otherNr);

            if (otherMove == Board.MOVE_NONE) {
                //check if he could've moved to our square, as that would make it a tie since it's his only option
                if (Board.getManhattanDistance(myX, myY, otherX, otherY) == 1) {
                    this.playout.onFinishPlayout(startingPlayer, myNr, SIM_DRAW, true);
                    return SIM_DRAW;
                } else {
                    this.playout.onFinishPlayout(startingPlayer, myNr, SIM_WIN, true);
                    return SIM_WIN; //he's stuck
                }
            }

            otherPos = Board.getPositionFromMove(otherX, otherY, otherMove);
            if (myPos == otherPos) {
                this.playout.onFinishPlayout(startingPlayer, myNr, SIM_DRAW, true);
                return SIM_DRAW; //tie
            }
            board.performMove(otherX, otherY, otherMove, otherNr, false);
            otherX = Board.posToX(otherPos);
            otherY = Board.posToY(otherPos);
        }

        int it = 0;
        while (true) {
            myMove = playout.getMove(board, myX, myY, myNr);
            otherMove = playout.getMove(board, otherX, otherY, otherNr);

            if (myMove == Board.MOVE_NONE) {
                if (otherMove == Board.MOVE_NONE) {
                    this.playout.onFinishPlayout(startingPlayer, myNr, SIM_DRAW, true);
                    return SIM_DRAW; //both players did not move
                } else {
                    this.playout.onFinishPlayout(startingPlayer, myNr, SIM_LOSS, true);
                    return SIM_LOSS; //I did not move
                }
            } else if (otherMove == Board.MOVE_NONE) {
                this.playout.onFinishPlayout(startingPlayer, myNr, SIM_WIN, true);
                return SIM_WIN; //other did not move
            }
            myPos = Board.getPositionFromMove(myX, myY, myMove);
            otherPos = Board.getPositionFromMove(otherX, otherY, otherMove);

            if (myPos == otherPos) {
                this.playout.onFinishPlayout(startingPlayer, myNr, SIM_DRAW, true);
                return SIM_DRAW;
            }

            //perform moves
            board.performMove(myX, myY, myMove, myNr, false);
            board.performMove(otherX, otherY, otherMove, otherNr, false);

            //update positions
            myX = Board.posToX(myPos);
            myY = Board.posToY(myPos);
            otherX = Board.posToX(otherPos);
            otherY = Board.posToY(otherPos);

            it++;
            if (applySimulationCutOff && it % 5 == 0) {
                double diff = spaceEval.compute(board, myNr);
                if (diff != 0 && !Double.isNaN(diff)) {
                    return (diff > 0) ? SIM_WIN : SIM_LOSS;
                }
            }
        }
    }

    private void propagatePessimisticBound(SolverNode s) {
        if (!s.isRoot()) {
            SolverNode n = (SolverNode) s.parent;
            double oldPess = n.pess;
            if (oldPess < s.pess) {
                if (!n.max) {
                    n.pess = s.pess;
                    propagatePessimisticBound(n);
                } else {
                    double minPess = Double.POSITIVE_INFINITY;
                    for (int i = 0; i < n.children.size(); i++) {
                        SolverNode c = (SolverNode) n.children.get(i);
                        if (c.pess < minPess) {
                            minPess = c.pess;
                        }
                    }
                    n.pess = minPess;
                    if (oldPess < n.pess) {
                        propagatePessimisticBound(n);
                    }
                }
            }
        }
    }

    private void propagateOptimisticBound(SolverNode s) {
        if (!s.isRoot()) {
            SolverNode n = (SolverNode) s.parent;
            double oldOpti = n.opti;
            if (oldOpti > s.opti) {
                if (!n.max) {
                    double maxOpti = Double.NEGATIVE_INFINITY;
                    for (int i = 0; i < n.children.size(); i++) {
                        SolverNode c = (SolverNode) n.children.get(i);
                        if (c.opti > maxOpti) {
                            maxOpti = c.opti;
                        }
                    }
                    n.opti = maxOpti;
                    if (oldOpti > n.opti) {
                        propagateOptimisticBound(n);
                    }
                } else {
                    n.opti = s.opti;
                    propagateOptimisticBound(n);
                }
            }
        }
    }

    protected void onComputeFirstMove(SolverNode theRoot) {
    }

    protected void onFinishComputation(SolverNode newRoot) {
    }

    protected SolverNode createNode(int player, SolverNode parent, int move, Board b) {
        SolverNode n;
        boolean max = (player == getNumber());
        if (parent == null) {
            n = new SolverNode(player, max);
        } else {
            n = new SolverNode(parent, player, move, max, b);
        }
        return n;
    }

    @Override
    public void reset() {
        turn = 0;
        root = null;
    }

    public static Player fromXml(org.w3c.dom.Node playerRoot, int num, Color color) {
        return fromXml(playerRoot, new NGramMCTSSolverPlayer(NGramMCTSSolverPlayer.class.getSimpleName(), num, color));
    }

    public static Player fromXml(org.w3c.dom.Node playerRoot, NGramMCTSSolverPlayer player) {
        NamedNodeMap attrs = playerRoot.getAttributes();
        player.description = "";
        if (attrs.getNamedItem("finalMove") != null) {
            try {
                Field field = FinalNodeSelectionStrategy.class.getField(attrs.getNamedItem("finalMove").getNodeValue());
                player.finalMove = (FinalNodeSelectionStrategy) field.get(null);
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

        player.playout = new NGramPlayout(15, 0.3, true);

        if (attrs.getNamedItem("selection") != null) {
            try {
                String selection = attrs.getNamedItem("selection").getNodeValue();
                if (selection.equalsIgnoreCase("UCT")) {
                    player.select = SolverSelectionStrategy.UCT;
                } else if (selection.equalsIgnoreCase("NGramUCT")) {
                    player.select = new SolverSelectionStrategy.NGramUCTSelection(player.playout.getNGram(), 10, 30, true);
                }
            } catch (Exception e) {
                e.printStackTrace();
            }
        } else {
            player.select = SolverSelectionStrategy.UCT;
        }

        if (attrs.getNamedItem("cut") != null) {
            try {
                String cutType = attrs.getNamedItem("cut").getNodeValue();
                if (cutType.equals("SPACE")) {
                    player.cutOff = CutOffStrategy.SPACE;
                } else {
                    player.cutOff = null;
                }
            } catch (Exception e) {
                player.cutOff = null;
                e.printStackTrace();
            }
        } else {
            player.cutOff = null;
        }

        if (attrs.getNamedItem("expCut") != null) {
            try {
                player.applyExpansionCutOff = Boolean.parseBoolean(attrs.getNamedItem("expCut").getNodeValue());
            } catch (Exception e) {
                e.printStackTrace();
            }
        } else {
            player.applyExpansionCutOff = false;
        }

        if (attrs.getNamedItem("simCut") != null) {
            try {
                player.applySimulationCutOff = Boolean.parseBoolean(attrs.getNamedItem("simCut").getNodeValue());
            } catch (Exception e) {
                e.printStackTrace();
            }
        } else {
            player.applySimulationCutOff = false;
        }

        if (attrs.getNamedItem("maxTurnTime") != null) {
            try {
                player.MAX_TURN_TIME = Long.parseLong(attrs.getNamedItem("maxTurnTime").getNodeValue());
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        player.description = String.format("select=%s playout=%s cut=%s final=%s expCut=" + player.applyExpansionCutOff + " simCut=" + player.applySimulationCutOff, player.select, player.playout, player.cutOff, player.finalMove);
        player.DEBUG = false;
        return player;
    }

    @Override
    public NGramMCTSSolverPlayer clone() {
        NGramMCTSSolverPlayer player = new NGramMCTSSolverPlayer(getName(), getNumber(), getColor());
        player.select = select;
        player.finalMove = finalMove;
        player.cutOff = cutOff;
        player.playout = playout;
        player.description = description;
        player.spaceEval = spaceEval;
        player.applyExpansionCutOff = applyExpansionCutOff;
        player.applySimulationCutOff = applySimulationCutOff;
        player.applySpaceEstimation = applySpaceEstimation;
        //player.DEBUG = true;
        return player;
    }
}